/*--- huffdec.c --------------------------- Listing 9-4 ---------
 * Purpose:         Uncompress a Huffman-compressed file
 *
 * Entry point:     int HuffDecode(FILE *infile, FILE *outfile)
 *
 *                  Will uncompress infile into outfile. Both
 *                  files should already be open in binary mode.
 *                  They will be closed by HuffDecode().
 *
 *                  HuffDecode() returns:
 *                      0: success
 *                      1: invalid signature byte
 *                      2: invalid header bytes
 *                      3: invalid data bytes
 *
 *
 * Switches:        DRIVER - compiles a test driver
 *                  DUMP - dump the tree after loading
 *-------------------------------------------------------------*/
#define DRIVER

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "huffman.h"

/* a simple tree */
struct _HuffTree {
    LinkType child[2];
} HuffTree[MAXNODES];

CountType HuffBytesIn;  /* number of bytes to decode */
LinkType HuffRoot;      /* the tree's root */
LinkType HuffCount;     /* the number of internal nodes */

#ifdef DUMP
static void HuffDump ( LinkType n )
{
    LinkType i;

    printf ( "root is %d\n", HuffRoot );
    printf ( "No.  Sym  Left  Right\n" );
    for ( i = 0; i <= n; i++ )
    {
        printf( "%3d. ", i );
        if ( i < MAXSYMBOLS )
        {
            if ( isprint ( i ))
                printf( " %c ", i );
            else
                printf ( "x%.2X", i );
        }
        else
            printf ( "n/a" );

        printf ( " %5d  %5d",
                HuffTree[i].child[LEFT],
                HuffTree[i].child[RIGHT] );

        printf ( "\n" );
    }
    printf ( "\n" );
}
#define DUMPTREE(x) HuffDump(x)
#else
#define DUMPTREE(x)
#endif

/* the actual decompression routine */
int HuffDecode ( FILE *infile, FILE *outfile )
{
    int retval = 0;
    LinkType i;
    char buffer[10];
    struct _Header header;
    CountType bytesout;
    int inbyte, bitno, mask, set;

    /* set all counts to zero and initialize symbols */
    memset ( HuffTree, 0, sizeof ( HuffTree ));

    /* check the signature */
    fgets ( buffer, strlen ( SIGNATURE ) + 2, infile );
    if ( strcmp ( buffer, SIGNATURE ))
    {
        retval = 1;
        goto done;
    }

    /* read in header bytes */

    fread ( &HuffRoot, sizeof ( HuffRoot), 1, infile );
    fread ( &HuffCount, sizeof ( HuffCount), 1, infile );
    fread ( &HuffBytesIn, sizeof ( HuffBytesIn), 1, infile );

    for ( i = 0;
            i < HuffCount + ( HuffRoot - MAXSYMBOLS + 1 ); i++)
    {
        fread ( &header, sizeof ( header ), 1, infile );
        HuffTree[header.index].child[0] = header.child[0];
        HuffTree[header.index].child[1] = header.child[1];
    }

    if ( ferror ( infile ))
    {
        retval = 2;
        goto done;
    }
    DUMPTREE ( HuffRoot );

    /* now, translate the data bytes */
    bitno = 8;
    for ( bytesout = 0; bytesout < HuffBytesIn; bytesout++ )
    {
        /* walk down the tree */
        i = HuffRoot;
        for ( ;; )
        {
            /* do we need a new input byte? */
            if ( bitno > 7 )
            {
                inbyte = fgetc ( infile );
                if ( inbyte == EOF )
                {
                    retval = 3;
                    goto done;
                }
                bitno = 0;
                mask = 0x80;
            }

            /* test the current bit */
            if ( inbyte & mask )
                set = 1;
            else
                set = 0;
            bitno++;
            mask >>= 1;

            /* walk down the tree */
            i = HuffTree[i].child[set];

            /* are we there yet? */
            if ( HuffTree[i].child[0] == -1 )
            {
                /* at the bottom -- write the character */
                fputc ( i, outfile );
                break;
            }
        }
    }

  done:
    fclose ( infile );
    fclose ( outfile );
    return ( retval );
}

#ifdef DRIVER
int main ( int argc, char *argv[] )
{
    FILE *infile, *outfile;
    int retval;

    if ( argc != 3 )
    {
        fprintf ( stderr, "Usage: huffdec infile outfile\n" );
        return ( EXIT_FAILURE );
    }

    infile = fopen ( argv[1], "r+b" );
    if ( infile == NULL )
    {
        fprintf ( stderr, "can't open %s for input\n", argv[1] );
        return ( EXIT_FAILURE );
    }

    outfile = fopen ( argv[2], "w+b" );
    if ( outfile == NULL )
    {
        fprintf ( stderr, "can't open %s for output\n", argv[2]);
        return ( EXIT_FAILURE );
    }

    if ( retval = HuffDecode ( infile, outfile ))
    {
        printf ( "decompression failed: " );
        if ( retval == 1 )
            printf ( "invalid signature byte\n" );
        if ( retval == 2 )
            printf ( "read error in header\n" );
        if ( retval == 3 )
            printf ( "read error in data\n" );
        else
            printf( "\n" );
        return ( retval );
    }
    else
    {
        printf ( "%s was expanded into %s\n",
                                        argv[1], argv[2]);
        return ( 0 );
    }
}
#endif
